/*  GStruct: data structure helpers for Java
 *  Copyright (C) 2011 Giulio Franco
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package gstruct.sequential;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Utility methods to perform additional operations on lists.
 * @author Giulio Franco <giulio_franco@msn.com>
 */
public final class ListUtils {
	private ListUtils() {}
	
	/**
	 * Returns a list of the required elements that are not contained in the universe.
	 * This method does not make any assumption about the objects
	 * contained in the collections. So, it performs a quadratic scan.
	 * If the objects implement a {@link Object#hashCode() hashCode}
	 * consistent with {@link Object#equals(Object) equals}, then it's more efficient
	 * to use {@link #getMissingFast(Enumeration, Iterable)}. 
	 * @param universe		Universe collection
	 * @param required		Collection of required items
	 * @return				List of object that are in required, but not in universe.
	 */
	public static <T> List<T> getMissing(Enumeration<? extends T> universe, Iterable<? extends T> required) {
		return getMissing(Collections.list(universe), required);
	}

	/**
	 * Returns a list of the required elements that are not contained in the universe.
	 * This method does not make any assumption about the objects
	 * contained in the collections. So, it performs a quadratic scan.
	 * If the objects implement a {@link Object#hashCode() hashCode}
	 * consistent with {@link Object#equals(Object) equals}, then it's more efficient
	 * to use {@link #getMissingFast(Iterable, Iterable)}. 
	 * @param universe		Universe collection
	 * @param required		Collection of required items
	 * @return				List of object that are in required, but not in universe.
	 */
	public static <T> List<T> getMissing(Iterable<? extends T> universe, Iterable<? extends T> required) {
		List<T> result = (required instanceof Collection) ? new ArrayList<T>(((Collection<? extends T>)required).size()) : new LinkedList<T>();
		
		for (T needle : required) {
			boolean found = false;
			for (T hay : universe) {
				if (needle.equals(hay)) {
					found = true;
					break;
				}
			}
			if (!found) {
				result.add(needle);
			}
		}
		
		return result;
	}
	
	/**
	 * Returns a list of the required elements that are not contained in the universe.
	 * This method assumes the objects of type T implement a
	 * {@link Object#hashCode() hashCode}
	 * consistent with {@link Object#equals(Object) equals}.
	 * If that's not how it is, then you should use {@link #getMissing(Enumeration, Iterable)}. 
	 * @param universe		Universe collection
	 * @param required		Collection of required items
	 * @return				List of object that are in required, but not in universe.
	 */
	public static <T> List<T> getMissingFast(Enumeration<? extends T> universe, Iterable<? extends T> required) {
		return getMissingFast(Collections.list(universe), required);
	}

	/**
	 * Returns a list of the required elements that are not contained in the universe.
	 * This method assumes the objects of type T implement a
	 * {@link Object#hashCode() hashCode}
	 * consistent with {@link Object#equals(Object) equals}.
	 * If that's not how it is, then you should use {@link #getMissing(Enumeration, Iterable)}. 
	 * @param universe		Universe collection
	 * @param required		Collection of required items
	 * @return				List of object that are in required, but not in universe.
	 */
	public static <T> List<T> getMissingFast(Iterable<? extends T> universe, Iterable<? extends T> required) {
		List<T> result = (required instanceof Collection) ? new ArrayList<T>(((Collection<? extends T>)required).size()) : new LinkedList<T>();
		Set<? extends T> set = new HashSet<>(new StaticallySizedIterable<>(universe));
		
		for (T needle : required) {
			if (!set.contains(needle)) {
				result.add(needle);
			}
		}
		
		return result;
	}
}
